#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->capacity == ps->top)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("relloc fail");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

void StackPop(ST* ps)
{
    assert(ps);
    if (StackEmpty(ps))
    {
        return;
    }
    ps->top--;
}

STDataType StackTop(ST* ps)
{
    assert(ps);
    if (StackEmpty(ps))
    {
        return -1;
    }
    return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}



typedef struct
{
    ST stack;
    ST help;
} SortedStack;


SortedStack* sortedStackCreate()
{
    SortedStack* s = (SortedStack*)malloc(sizeof(SortedStack));
    StackInit(&s->stack);
    StackInit(&s->help);
    return s;
}

void sortedStackPush(SortedStack* obj, int val)
{
    StackPush(&obj->stack, val);
    while (!StackEmpty(&obj->stack))
    {
        int top = StackTop(&obj->stack);
        StackPop(&obj->stack);
        while (!StackEmpty(&obj->help) && StackTop(&obj->help) > top)
        {
            StackPush(&obj->stack, StackTop(&obj->help));
            StackPop(&obj->help);
        }
        StackPush(&obj->help, top);
    }
    while (!StackEmpty(&obj->help))
    {
        int top = StackTop(&obj->help);
        StackPush(&obj->stack, top);
        StackPop(&obj->help);
    }
}

void sortedStackPop(SortedStack* obj)
{
    StackPop(&obj->stack);
}

int sortedStackPeek(SortedStack* obj)
{
    return StackTop(&obj->stack);
}

bool sortedStackIsEmpty(SortedStack* obj)
{
    return StackEmpty(&obj->stack);
}

void sortedStackFree(SortedStack* obj)
{
    StackDestroy(&obj->stack);
    StackDestroy(&obj->help);
    free(obj);
}
